package com.xigua._树;

import com.xigua.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/4/2915:51
 */
public class _113_路径总和_2 {


    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) return  ans;
        dfs(root,targetSum,new ArrayList<>());
        return ans;
    }

    void dfs(TreeNode root, int targetSum, ArrayList<Integer> list) {
        list.add(root.val);
        if (root.val == targetSum && root.left == null && root.right == null){
            ans.add(list);
            return;
        }else if (root.left == null && root.right ==null)return;
        if (root.left != null && root.right != null){
            ArrayList<Integer> leftList = new ArrayList<>(list);
            dfs(root.right,targetSum-root.val,list);
            dfs(root.left,targetSum-root.val,leftList);
        }else if (root.left ==null ){
               dfs(root.right,targetSum-root.val,list);
        } else if (root.right == null){
            dfs(root.left,targetSum-root.val,list);
        }
    }

}
